Interactive certificate for the verification of Wiedemann's Krylov sequence: application to the certification of the determinant, the minimal and the characteristic polynomials of sparse matrices
Identifieur interne : 000455 ( Main/Exploration ); précédent : 000454; suivant : 000456Interactive certificate for the verification of Wiedemann's Krylov sequence: application to the certification of the determinant, the minimal and the characteristic polynomials of sparse matrices
Auteurs : Jean-Guillaume Dumas [France] ; Erich Kaltofen [États-Unis] ; Emmanuel Thomé [France]Source :
Abstract
Certificates to a linear algebra computation are additional data structures for each output, which can be used by a—possibly randomized— verification algorithm that proves the correctness of each output. Wiede-mann's algorithm projects the Krylov sequence obtained by repeatedly multiplying a vector by a matrix to obtain a linearly recurrent sequence. The minimal polynomial of this sequence divides the minimal polynomial of the matrix. For instance, if the n×n input matrix is sparse with n 1+o(1) non-zero entries, the computation of the sequence is quadratic in the dimension of the matrix while the computation of the minimal polynomial is n 1+o(1) , once that projected Krylov sequence is obtained. In this paper we give algorithms that compute certificates for the Krylov sequence of sparse or structured n × n matrices over an abstract field, whose Monte Carlo verification complexity can be made essentially linear. As an application this gives certificates for the determinant, the minimal and characteristic polynomials of sparse or structured matrices at the same cost.
Url:
Affiliations:
- France, États-Unis
- Auvergne-Rhône-Alpes, Grand Est, Lorraine (région), Rhône-Alpes
- Grenoble, Metz, Nancy
- Université Joseph Fourier, Université Pierre-Mendès-France, Université de Grenoble, Université de Lorraine
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 002C20
- to stream Hal, to step Curation: 002C20
- to stream Hal, to step Checkpoint: 000433
- to stream Main, to step Merge: 000455
- to stream Main, to step Curation: 000455
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Interactive certificate for the verification of Wiedemann's Krylov sequence: application to the certification of the determinant, the minimal and the characteristic polynomials of sparse matrices</title>
<author><name sortKey="Dumas, Jean Guillaume" sort="Dumas, Jean Guillaume" uniqKey="Dumas J" first="Jean-Guillaume" last="Dumas">Jean-Guillaume Dumas</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-388448" status="VALID"><orgName>Calculs Algébriques et Systèmes Dynamiques</orgName>
<orgName type="acronym">CASYS</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
<listRelation><relation active="#struct-24474" type="direct"></relation>
<relation active="#struct-3886" type="indirect"></relation>
<relation active="#struct-51016" type="indirect"></relation>
<relation active="#struct-300339" type="indirect"></relation>
<relation name="UMR5224" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-24474" type="direct"><org type="laboratory" xml:id="struct-24474" status="VALID"><orgName>Laboratoire Jean Kuntzmann</orgName>
<orgName type="acronym">LJK</orgName>
<desc><address><addrLine>Tour IRMA 51 rue des Mathématiques - 53 38041 GRENOBLE CEDEX 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://ljk.imag.fr</ref>
</desc>
<listRelation><relation active="#struct-3886" type="direct"></relation>
<relation active="#struct-51016" type="direct"></relation>
<relation active="#struct-300339" type="direct"></relation>
<relation name="UMR5224" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-3886" type="indirect"><org type="institution" xml:id="struct-3886" status="OLD"><orgName>Université Pierre Mendès France</orgName>
<orgName type="acronym">Grenoble 2 UPMF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 47 - 38040 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.upmf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-51016" type="indirect"><org type="institution" xml:id="struct-51016" status="OLD"><orgName>Université Joseph Fourier</orgName>
<orgName type="acronym">UJF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 53 - 38041 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ujf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300339" type="indirect"><org type="institution" xml:id="struct-300339" status="VALID"><orgName>Institut Polytechnique de Grenoble - Grenoble Institute of Technology</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR5224" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Pierre-Mendès-France</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Joseph Fourier</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
</affiliation>
</author>
<author><name sortKey="Kaltofen, Erich" sort="Kaltofen, Erich" uniqKey="Kaltofen E" first="Erich" last="Kaltofen">Erich Kaltofen</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-169897" status="VALID"><orgName>Department of Mathematics [Raleigh]</orgName>
<orgName type="acronym">NCSU</orgName>
<desc><address><addrLine>Box 8205, Raleigh, NC 27695-8205, USA</addrLine>
<country key="US"></country>
</address>
<ref type="url">https://www.math.ncsu.edu/</ref>
</desc>
<listRelation><relation active="#struct-306579" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-306579" type="direct"><org type="institution" xml:id="struct-306579" status="VALID"><orgName>North Carolina State University [Raleigh]</orgName>
<orgName type="acronym">NCSU</orgName>
<desc><address><addrLine>Raleigh, NC 27695</addrLine>
<country key="US"></country>
</address>
<ref type="url">https://www.ncsu.edu/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Thome, Emmanuel" sort="Thome, Emmanuel" uniqKey="Thome E" first="Emmanuel" last="Thomé">Emmanuel Thomé</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-119560" status="VALID"><idno type="RNSR">201020971F</idno>
<orgName>Cryptology, Arithmetic: Hardware and Software</orgName>
<orgName type="acronym">CARAMEL</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/caramel</ref>
</desc>
<listRelation><relation active="#struct-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423083" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/nancy</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-423083" type="direct"><org type="department" xml:id="struct-423083" status="VALID"><orgName>Department of Algorithms, Computation, Image and Geometry</orgName>
<orgName type="acronym">LORIA - ALGO</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref>
</desc>
<listRelation><relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<settlement type="city">Metz</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01171249</idno>
<idno type="halId">hal-01171249</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-01171249</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-01171249</idno>
<date when="2015-07-03">2015-07-03</date>
<idno type="wicri:Area/Hal/Corpus">002C20</idno>
<idno type="wicri:Area/Hal/Curation">002C20</idno>
<idno type="wicri:Area/Hal/Checkpoint">000433</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000433</idno>
<idno type="wicri:Area/Main/Merge">000455</idno>
<idno type="wicri:Area/Main/Curation">000455</idno>
<idno type="wicri:Area/Main/Exploration">000455</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Interactive certificate for the verification of Wiedemann's Krylov sequence: application to the certification of the determinant, the minimal and the characteristic polynomials of sparse matrices</title>
<author><name sortKey="Dumas, Jean Guillaume" sort="Dumas, Jean Guillaume" uniqKey="Dumas J" first="Jean-Guillaume" last="Dumas">Jean-Guillaume Dumas</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-388448" status="VALID"><orgName>Calculs Algébriques et Systèmes Dynamiques</orgName>
<orgName type="acronym">CASYS</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
<listRelation><relation active="#struct-24474" type="direct"></relation>
<relation active="#struct-3886" type="indirect"></relation>
<relation active="#struct-51016" type="indirect"></relation>
<relation active="#struct-300339" type="indirect"></relation>
<relation name="UMR5224" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-24474" type="direct"><org type="laboratory" xml:id="struct-24474" status="VALID"><orgName>Laboratoire Jean Kuntzmann</orgName>
<orgName type="acronym">LJK</orgName>
<desc><address><addrLine>Tour IRMA 51 rue des Mathématiques - 53 38041 GRENOBLE CEDEX 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://ljk.imag.fr</ref>
</desc>
<listRelation><relation active="#struct-3886" type="direct"></relation>
<relation active="#struct-51016" type="direct"></relation>
<relation active="#struct-300339" type="direct"></relation>
<relation name="UMR5224" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-3886" type="indirect"><org type="institution" xml:id="struct-3886" status="OLD"><orgName>Université Pierre Mendès France</orgName>
<orgName type="acronym">Grenoble 2 UPMF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 47 - 38040 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.upmf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-51016" type="indirect"><org type="institution" xml:id="struct-51016" status="OLD"><orgName>Université Joseph Fourier</orgName>
<orgName type="acronym">UJF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 53 - 38041 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ujf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300339" type="indirect"><org type="institution" xml:id="struct-300339" status="VALID"><orgName>Institut Polytechnique de Grenoble - Grenoble Institute of Technology</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR5224" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Pierre-Mendès-France</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Joseph Fourier</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
</affiliation>
</author>
<author><name sortKey="Kaltofen, Erich" sort="Kaltofen, Erich" uniqKey="Kaltofen E" first="Erich" last="Kaltofen">Erich Kaltofen</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-169897" status="VALID"><orgName>Department of Mathematics [Raleigh]</orgName>
<orgName type="acronym">NCSU</orgName>
<desc><address><addrLine>Box 8205, Raleigh, NC 27695-8205, USA</addrLine>
<country key="US"></country>
</address>
<ref type="url">https://www.math.ncsu.edu/</ref>
</desc>
<listRelation><relation active="#struct-306579" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-306579" type="direct"><org type="institution" xml:id="struct-306579" status="VALID"><orgName>North Carolina State University [Raleigh]</orgName>
<orgName type="acronym">NCSU</orgName>
<desc><address><addrLine>Raleigh, NC 27695</addrLine>
<country key="US"></country>
</address>
<ref type="url">https://www.ncsu.edu/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Thome, Emmanuel" sort="Thome, Emmanuel" uniqKey="Thome E" first="Emmanuel" last="Thomé">Emmanuel Thomé</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-119560" status="VALID"><idno type="RNSR">201020971F</idno>
<orgName>Cryptology, Arithmetic: Hardware and Software</orgName>
<orgName type="acronym">CARAMEL</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/caramel</ref>
</desc>
<listRelation><relation active="#struct-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423083" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/nancy</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-423083" type="direct"><org type="department" xml:id="struct-423083" status="VALID"><orgName>Department of Algorithms, Computation, Image and Geometry</orgName>
<orgName type="acronym">LORIA - ALGO</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref>
</desc>
<listRelation><relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<settlement type="city">Metz</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Certificates to a linear algebra computation are additional data structures for each output, which can be used by a—possibly randomized— verification algorithm that proves the correctness of each output. Wiede-mann's algorithm projects the Krylov sequence obtained by repeatedly multiplying a vector by a matrix to obtain a linearly recurrent sequence. The minimal polynomial of this sequence divides the minimal polynomial of the matrix. For instance, if the n×n input matrix is sparse with n 1+o(1) non-zero entries, the computation of the sequence is quadratic in the dimension of the matrix while the computation of the minimal polynomial is n 1+o(1) , once that projected Krylov sequence is obtained. In this paper we give algorithms that compute certificates for the Krylov sequence of sparse or structured n × n matrices over an abstract field, whose Monte Carlo verification complexity can be made essentially linear. As an application this gives certificates for the determinant, the minimal and characteristic polynomials of sparse or structured matrices at the same cost.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
<region><li>Auvergne-Rhône-Alpes</li>
<li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Rhône-Alpes</li>
</region>
<settlement><li>Grenoble</li>
<li>Metz</li>
<li>Nancy</li>
</settlement>
<orgName><li>Université Joseph Fourier</li>
<li>Université Pierre-Mendès-France</li>
<li>Université de Grenoble</li>
<li>Université de Lorraine</li>
</orgName>
</list>
<tree><country name="France"><region name="Auvergne-Rhône-Alpes"><name sortKey="Dumas, Jean Guillaume" sort="Dumas, Jean Guillaume" uniqKey="Dumas J" first="Jean-Guillaume" last="Dumas">Jean-Guillaume Dumas</name>
</region>
<name sortKey="Thome, Emmanuel" sort="Thome, Emmanuel" uniqKey="Thome E" first="Emmanuel" last="Thomé">Emmanuel Thomé</name>
</country>
<country name="États-Unis"><noRegion><name sortKey="Kaltofen, Erich" sort="Kaltofen, Erich" uniqKey="Kaltofen E" first="Erich" last="Kaltofen">Erich Kaltofen</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000455 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000455 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= Hal:hal-01171249 |texte= Interactive certificate for the verification of Wiedemann's Krylov sequence: application to the certification of the determinant, the minimal and the characteristic polynomials of sparse matrices }}
This area was generated with Dilib version V0.6.33. |